;; helper functions
(define (accumulate op init seq)
  (if (null? seq)
      init
      (op (car seq)
          (accumulate op init (cdr seq)))))


(define (accumulate op init seq) (if (null? seq) init (op (car seq) (accumulate op init (cdr seq)))))


(define (flatmap proc seq)
  (accumulate append '() (map proc seq)))

(define (enumerate-interval low high)
  (if (> low high)
      '()
      (cons low (enumerate-interval (+ low 1) high))))


;; data structures and basic functions for board
(define (make-queen row col) (list row col))
(define (get-row queen) (car queen))
(define (get-col queen) (car (cdr queen)))

(define (same-col? q1 q2) (= (get-col q1) (get-col q2)))
(define (same-diag? q1 q2) 
  (= 
   (abs (- (get-row q1) (get-row q2))) 
   (abs (- (get-col q1) (get-col q2)))))

(define (attacks? q1 q2)
  (or (same-col? q1 q2) (same-diag? q1 q2)))

(define (safe? newq qlist)
  (cond 
    ((null? qlist) #t)
    ((attacks? newq (car qlist)) #f)
    (else (safe? newq (cdr qlist)))))

(define (safe-board? qlist)
  (let 
    ((newq (car qlist))
     (rest (cdr qlist)))
    (safe? newq rest)))


;; the depth-first search for queens
(define (queens board-size)
  (define (queen-rows k sols)
    (if (= k board-size)
        sols
	(queen-rows (+ k 1) 
          (filter 
            (lambda (board) (safe-board? board))
            (flatmap 
	      (lambda (rest-queens)
	        (map (lambda (new-col)
	  	     (cons (list k new-col) rest-queens))
	  	   (enumerate-interval 1 board-size)))
	      sols)))))
  (queen-rows 0 (list '())))



(length (queens 8))

